#include "procthread.h"
#include "src\datamaker.h"
#include <QElapsedTimer>

SpawnDataThread::SpawnDataThread(QObject *parent) : QThread(parent) {

}

void SpawnDataThread::receiveSize(int n, int m, bool isEdge) {
    m_n = n;
    m_m = m;
    m_isEdge = isEdge;
}

void SpawnDataThread::run() {
    //生成随机数据
    DataMaker &dataMaker = DataMaker::GetInstance();
    dataMaker.isEdge = m_isEdge;
    dataMaker.InitParas(m_n, m_m);
    dataMaker.SpawnData();

    emit sendSuccessful(dataMaker.isSuccessful);
}

ProcThread::ProcThread(QObject *parent) : QThread(parent) {
}

void ProcThread::receiveSize(int squareSize, int interval) {
    m_squareSize = squareSize;
    m_interval = interval;
}

void ProcThread::run() {
    // 读入迷宫数据
    InputData();

    // 图形化迷宫初始布局
    SpawnLayout();
}

void ProcThread::SpawnLayout() {
    QColor color;
    // 绘制迷宫
    for (int i = 0; i < m_n; ++i) {
        for (int j = 0; j < m_m; ++j) {
            // 通路为灰色 墙为黑色
            color = m_mp[i][j] ? Qt::lightGray : Qt::black;
            // 根据大小和位置设置画布上的位置
            emit drawProc(1, i * m_squareSize + m_interval * (i + 1), j * m_squareSize + m_interval * (j + 1), color);
        }
    }
    // 图形化起点与终点
    // 起点设为绿色 终点为红色
    emit drawProc(0, m_start.first, m_start.second, Qt::green);
    emit drawProc(0, m_end.first, m_end.second, Qt::red);
    //停下2s(2000ms)
    QThread::msleep(800);
}

void ProcThread::InputData() {
    ifstream dataFile("data.in");
    dataFile >> m_n >> m_m;                       // 迷宫大小
    dataFile >> m_start.first >> m_start.second >> m_end.first >> m_end.second; // 起点终点
    m_mp.resize(m_n);
    for (int i = 0; i < m_n; i++) // 是否能通过
        for (int j = 0; j < m_m; j++) {
            int tmp;
            dataFile >> tmp;
            m_mp[i].push_back(tmp);
        }
    for (int i = 0; i < m_n; i++) {
        for (int j = 0; j < m_m; j++) {
            dataFile >> m_edge[ptp(i, j, i - 1, j)]; // up
            dataFile >> m_edge[ptp(i, j, i, j + 1)]; // right
            dataFile >> m_edge[ptp(i, j, i + 1, j)]; // down
            dataFile >> m_edge[ptp(i, j, i, j - 1)]; // left
        }
    }
    // for(int i=0;i<mp.size();i++)
    // {
    //     for(int j=0;j<mp[i].size();j++)
    //         cout << mp[i][j] << ' ';
    //     cout << endl;
    // }
}

AStarProcThread::AStarProcThread(QObject *parent)
        : ProcThread(parent) {

}

void AStarProcThread::run() {
    //生成初始迷宫图形
    ProcThread::run();
    //记录时间
    QElapsedTimer time;
    time.start();
    sleepTimes = 0;

    vector<vector<PII>> AS_look; //  A*每一步扩展到的点
    vector<PII > AS_way;          // A*计算出的路径

    priority_queue<pair<int, PII>> q; // 优先队列
    map<PII, PII > last;               // 记录这个点的路径
    map<PII, int> dist, vis;          // dist:这个点的最短路径  vis:节点是否访问过

    for (int i = 0; i < m_n; i++)
        for (int j = 0; j < m_m; j++)
            dist[{i, j}] = INT_MAX, vis[{i, j}] = 0; // 初始化

    auto vised = [&](pair<int, PII > x) {
        if (vis[{x.second.first, x.second.second}] == 1)
            return 1;
        vis[{x.second.first, x.second.second}] = 1;
        return 0;
    }; // 询问是否访问过

    auto f_dist = [&](PII x) {
        return abs(x.first - m_end.first) + abs(x.second - m_end.second);
    }; // 求预估值

    q.push({0, m_start}); // 放入起点
    AS_look.resize(1);
    AS_look[0].push_back(m_start); // 第一次扩展的点
    dist[m_start] = 0;             // 起点的最短路为0

    while (!q.empty()) {
        auto now = q.top();
        q.pop(); // 取出队头点

        if (now.second == m_end)
            break; // 找到了终点,结束

        if (vised(now)) // 判断是否访问过,访问过节点则跳过
            continue;

        vector<PII > look_tmp;
        for (int i = 0; i < 4; i++) {
            PII next = {now.second.first + m_dx[i], now.second.second + m_dy[i]}; // 取得下一个点
            if (0 <= next.first && next.first < m_n && 0 <= next.second && next.second < m_m) { // 如果该点合法
                if (m_mp[next.first][next.second] == 1) { // 如果该点能走
                    if (dist[next] >
                        dist[now.second] + m_edge[ptp(now.second.first, now.second.second, next.first, next.second)] +
                        f_dist(next)) { // 如果从now走到next的路径比原来next的路径更优
                        dist[next] = dist[now.second] +
                                     m_edge[ptp(now.second.first, now.second.second, next.first, next.second)];
                        // 更新next的最短路
                        q.push({-(dist[{next.first, next.second}] + f_dist(next)), next}); // 放入队列
                        last[next] = now.second;                                  // 记录来时的点
                        look_tmp.push_back(next);                                 // 记录扩展的点
                        emit drawProc(0, next.first, next.second, Qt::blue);
                        QThread::msleep(SLEEP_TIME);
                        ++sleepTimes;
                    }
                }
            }
        }
        if (!look_tmp.empty())
            AS_look.push_back(look_tmp); // 如果本次循环扩展到了新点,则记录
    }

    long long spentTime = time.elapsed() - SLEEP_TIME * sleepTimes;
    //重新显示一下起点和终点 起点设为绿色 终点为红色
    emit drawProc(0, m_start.first, m_start.second, Qt::green);
    emit drawProc(0, m_end.first, m_end.second, Qt::red);
    AS_ans = dist[m_end]; // 记录起点到终点的最短路
    stack<PII > s;
    s.push(m_end);
    while (s.top() != m_start)
        s.push(last[s.top()]);
    while (!s.empty()) {
        AS_way.push_back(s.top());
        emit drawProc(0, s.top().first, s.top().second, Qt::green);
        QThread::msleep(SLEEP_TIME);
        ++sleepTimes;
        s.pop();
    } // 求路径

    emit sendSpentTime(spentTime);
    // /* 下列代码为调试时使用*/
    // cout << AS_ans << endl; // 输出所求最少花费
    // int debug_mp[10][10];   // 每次扩展到的点
    // memset(debug_mp, 0, sizeof debug_mp);
    // for (auto i : AS_look)
    // {
    //     for (auto j : i)
    //     {
    //         cout << "(" << j.first << "," << j.second << ") ";
    //         debug_mp[j.first][j.second] = 1;
    //     }
    //     cout << endl;
    //     for (int I = 0; I < n; I++)
    //     {
    //         for (int J = 0; J < m; J++)
    //             cout << debug_mp[I][J] << ' ';
    //         cout << endl;
    //     }
    //     cout << endl;
    // }
    // for (auto i : AS_way) // 输出最短路径
    //     cout << "(" << i.first << ',' << i.second << ')' << ' ';
    // cout << endl;
}

BfsProcThread::BfsProcThread(QObject *parent)
        : ProcThread(parent) {

}

void BfsProcThread::run() {
    //生成初始迷宫图形
    ProcThread::run();
    //记录时间
    QElapsedTimer time;
    time.start();
    sleepTimes = 0;

    //  --------bfs----------
    vector<PII > bfs_way;
    queue<PII > q;
    map<PII, bool> tmp;
    map<PII, PII > last;
    q.push(m_start);
    tmp[m_start] = true;

    while (!q.empty()) {
        PII now = q.front();
        q.pop();
        // cout << now.first << ' ' << now.second << endl;

        for (int i = 0; i < 4; i++) {
            PII next = {now.first + m_dx[i], now.second + m_dy[i]};
            if (0 <= next.first && next.first < m_n && 0 <= next.second && next.second < m_m)
                if (tmp[next] == 0)
                    if (m_mp[next.first][next.second] == 1) {
                        tmp[next] = true;
                        last[next] = now;
                        q.push(next);
                        emit drawProc(0, next.first, next.second, Qt::blue);
                        QThread::msleep(SLEEP_TIME);
                        ++sleepTimes;
                    }
        }
    }

    stack<PII > s;
    PII now = m_end;
    while (now != m_start)
        s.push(now), now = last[now];
    bfs_way.push_back(m_start);
    while (!s.empty()) {
        bfs_way.push_back(s.top());
        s.pop();
    }

    long long spentTime = time.elapsed() - SLEEP_TIME * sleepTimes;
    //重新显示一下起点和终点 起点设为绿色 终点为红色
    emit drawProc(0, m_start.first, m_start.second, Qt::green);
    emit drawProc(0, m_end.first, m_end.second, Qt::red);
    for (auto i: bfs_way) {
        emit drawProc(0, i.first, i.second, Qt::green);
        QThread::msleep(SLEEP_TIME);
        ++sleepTimes;
    }

    emit sendSpentTime(spentTime);

}

DfsProcThread::DfsProcThread(QObject *parent)
        : ProcThread(parent) {

}

void DfsProcThread::run() {
    //生成初始迷宫图形
    ProcThread::run();
    //记录时间
    QElapsedTimer time;
    time.start();
    sleepTimes = 0;

    find_ans=0;
    m_faw_tmp.clear();
    m_way.clear();

    vector<PII > tmp;
    tmp.clear();
    m_faw_tmp[m_start] = true;
    dfs(m_start, tmp);

    emit drawProc(0, m_start.first, m_start.second, Qt::green);
    emit drawProc(0, m_end.first, m_end.second, Qt::red);

    for (int i=0;i<=0;i++) {
        for (auto j: m_way[0]) {
            emit drawProc(0, j.first, j.second, Qt::green);
            QThread::msleep(SLEEP_TIME);
            ++sleepTimes;
        }
    }

    long long spentTime = time.elapsed() - SLEEP_TIME * sleepTimes;
    //重新显示一下起点和终点 起点设为绿色 终点为红色
    emit sendSpentTime(spentTime);
}

DijkstraProcThread::DijkstraProcThread(QObject *parent)
        : ProcThread(parent) {

}

void DijkstraProcThread::run() {
    //生成初始迷宫图形
    ProcThread::run();
    //记录时间
    QElapsedTimer time;
    time.start();
    sleepTimes = 0;

    vector<vector<PII>> djstr_look; // 迪杰斯特拉每一步扩展到的点
    vector<PII > djstr_way;          // 迪杰斯特拉计算出的路径

    priority_queue<pair<int, PII>> q; // 优先队列
    map<PII, PII > last;               // 记录这个点的路径
    map<PII, int> dist, vis;          // dist:这个点的最短路径  vis:节点是否访问过

    for (int i = 0; i < m_n; i++)
        for (int j = 0; j < m_m; j++)
            dist[{i, j}] = INT_MAX, vis[{i, j}] = 0; // 初始化

    auto vised = [&](pair<int, PII > x) {
        if (vis[{x.second.first, x.second.second}] == 1)
            return 1;
        vis[{x.second.first, x.second.second}] = 1;
        return 0;
    }; // 询问是否访问过

    q.push({0, m_start}); // 放入起点
    djstr_look.resize(1);
    djstr_look[0].push_back(m_start); // 第一次扩展的点
    dist[m_start] = 0;                // 起点的最短路为0

    while (!q.empty()) {
        auto now = q.top();
        q.pop(); // 取出队头点

        if (vised(now)) // 判断是否访问过,访问过节点则跳过
            continue;

        vector<PII > look_tmp;
        for (int i = 0; i < 4; i++) {
            PII next = {now.second.first + m_dx[i], now.second.second + m_dy[i]}; // 取得下一个点
            if (0 <= next.first && next.first < m_n && 0 <= next.second && next.second < m_m) { // 如果该点合法
                if (m_mp[next.first][next.second] == 1) { // 如果该点能走
                    if (dist[next] > dist[now.second] + m_edge[ptp(now.second.first, now.second.second, next.first,
                                                                   next.second)]) { // 如果从now走到next的路径比原来next的路径更优
                        dist[next] = dist[now.second] +
                                     m_edge[ptp(now.second.first, now.second.second, next.first, next.second)];
                        // 更新next的最短路
                        q.push({-dist[{next.first, next.second}], next}); // 放入队列
                        last[next] = now.second;                 // 记录来时的点
                        look_tmp.push_back(next);                // 记录扩展的点
                        emit drawProc(0, next.first, next.second, Qt::blue);
                        QThread::msleep(SLEEP_TIME);
                        ++sleepTimes;
                    }
                }
            }
        }
        if (!look_tmp.empty())
            djstr_look.push_back(look_tmp); // 如果本次循环扩展到了新点,则记录
    }

    djstr_ans = dist[m_end]; // 记录起点到终点的最短路
    stack<PII > s;
    s.push(m_end);
    while (s.top() != m_start)
        s.push(last[s.top()]);
    while (!s.empty()) {
        djstr_way.push_back(s.top());
        s.pop();
    } // 求路径

    long long spentTime = time.elapsed() - SLEEP_TIME * sleepTimes;
    //重新显示一下起点和终点 起点设为绿色 终点为红色
    emit drawProc(0, m_start.first, m_start.second, Qt::green);
    emit drawProc(0, m_end.first, m_end.second, Qt::red);
    // /* 下列代码为调试时使用*/
    // cout << djstr_ans << endl; // 输出所求最少花费
    // int debug_mp[10][10];      // 每次扩展到的点
    // memset(debug_mp, 0, sizeof debug_mp);
    // for (auto i : djstr_look)
    // {
    //     for (auto j : i)
    //     {
    //         cout << "(" << j.first << "," << j.second << ") ";
    //         debug_mp[j.first][j.second] = 1;
    //     }
    //     cout << endl;
    //     for (int I = 0; I < n; I++)
    //     {
    //         for (int J = 0; J < m; J++)
    //             cout << debug_mp[I][J] << ' ';
    //         cout << endl;
    //     }
    //     cout << endl;
    // }
    for (auto i: djstr_way) // 输出最短路径
    {
        emit drawProc(0, i.first, i.second, Qt::green);
        QThread::msleep(SLEEP_TIME);
        ++sleepTimes;
    }
    emit sendSpentTime(spentTime);
}
